package com.example.demo.lc.str;

import java.util.Arrays;

/**
* @author wzh
* @date 2021/7/12 5:32 下午
* @Description   leetcode -28
 * 
 * 实现strStr()函数。
 *
 * 给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
 *
 * （ev(G)为基本复杂度，iv(G)为设计复杂度，v(G)为圈复杂度）
 *
 * 说明：
 *
 * 当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
 *
 * 对于本题而言，当needle是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的indexOf()定义相符。
 *
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/implement-strstr
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class LeetCode28 {

    public static void main(String[] args) {
        String haystack = "a", needle = "";
        //String haystack = "aaaaa", needle = "bba";
        //String haystack = "a", needle = "a";
        //String haystack = "a", needle = "ab";
        //String haystack = "aa", needle = "aa";
        //String haystack = "aa", needle = "a";
        //String haystack = "mississippi", needle = "issip";
        //System.out.println(strStr(haystack,needle));

        //kmp
        int kmp = kmp(haystack, needle);
        System.out.println(kmp);
        //String str = "aababcd";
        //int[] next = getNext(str);
        //System.out.println(Arrays.toString(next));
        /*char[] source = haystack.toCharArray();
        char[] target = needle.toCharArray();
        int i = indexOf(source, 0, source.length, target, 0, target.length, 0);*/
        //int i = indexOf(haystack, needle);
        //System.out.println(i);
    }


    /**
    * @author wzh
    * @date 2021/7/12 5:33 下午
    * @Description    暴力破解
    */
    public static int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        char[] hay = haystack.toCharArray();
        char[] need = needle.toCharArray();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (hay[i + j] != need[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }

    public static int kmp(String haystack, String needle) {
        char[] hay = haystack.toCharArray();
        char[] need = needle.toCharArray();
        if(need.length == 0)return 0;
        int i = 0,j=0;
        int[] next = getNext(needle);
        while(i<hay.length && j<need.length){
            if(j == -1 || hay[i] == need[j]){
                i++;
                j++;
            }else{
                j = next[j];
            }
        }
        if(needle.length() == j){
            return i-j;
        }else{
            return -1;
        }
    }

    public static int[] getNext(String need) {
        char[] p = need.toCharArray();
        int[] next = new int[p.length];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < p.length - 1) {
            //p[k]表示前缀，p[j]表示后缀
            if (k == -1 || p[k] == p[j]) {
                //即当p[k] == p[j]时，next[j+1] == next[j] + 1=k+1
                k++;
                j++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        return next;
    }


    static int indexOf(char[] source, int sourceOffset, int sourceCount,
                       char[] target, int targetOffset, int targetCount,
                       int fromIndex) {
        if (fromIndex >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }
        if (fromIndex < 0) {
            fromIndex = 0;
        }
        if (targetCount == 0) {
            return fromIndex;
        }

        char first = target[targetOffset];
        int max = sourceOffset + (sourceCount - targetCount);

        for (int i = sourceOffset + fromIndex; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + targetCount - 1;
                for (int k = targetOffset + 1; j < end && source[j]
                        == target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i - sourceOffset;
                }
            }
        }
        return -1;
    }

    static int indexOf(String hay,String need) {
        char[] source = hay.toCharArray();
        char[] target = need.toCharArray();
        if (0 == source.length) {
            return (target.length == 0 ? 0 : -1);
        }
        if (need.length() == 0) {
            return 0;
        }
        char first = target[0];
        int max = source.length - target.length;
        for (int i = 0; i <= max; i++) {
            /* Look for first character. */
            if (source[i] != first) {
                while (++i <= max && source[i] != first);
            }

            /* Found first character, now look at the rest of v2 */
            if (i <= max) {
                int j = i + 1;
                int end = j + target.length - 1;
                for (int k =  1; j < end && source[j]
                        == target[k]; j++, k++);

                if (j == end) {
                    /* Found whole string. */
                    return i;
                }
            }
        }
        return -1;
    }
}
